package com.qjc.demo.train.strmatch.trie;

/**
 * @ClassName: Trie
 * @Description: Trie 树，也叫“字典树”（多叉树）。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，
 * @Author: qjc
 * @Date: 2022/5/2 6:03 PM
 */
public class Trie {
    // 根节点
    TrieNode root = new TrieNode('/');

    // 往trie树插入一个字符
    public void insert(char[] text) {
        TrieNode p = root;
        for (int i = 0; i < text.length; i++) {
            int index = text[i] - 97;
            if (p.children[index] == null) {
                // 还没存放，则放进去
                TrieNode trieNode = new TrieNode(text[i]);
                p.children[index] = trieNode;
            }
            // 说明已经放过了，直接指向它就行
            p = p.children[index];
        }
        // 最后肯定是叶子结点
        p.isLeaf = true;
    }

    // 在Trie树中查找一个字符串
    public boolean find(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; i++) {
            int index = pattern[i] - 97;
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (!p.isLeaf) return false; // 不能完全匹配，只是前缀
        else return true;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("hello".toCharArray());
        trie.insert("her".toCharArray());
        trie.insert("hi".toCharArray());
        trie.insert("how".toCharArray());
        trie.insert("see".toCharArray());
        trie.insert("so".toCharArray());

        System.out.println(trie.find("how".toCharArray()));
    }

}
